Chapter 4
2D Circular Geometry Kernel

Table of Contents

4.1   Introduction

The goal of the circular kernel is to offer to the user a large set of functionalities on circles and circular arcs in the plane. All the choices (interface, robustness, representation, and so on) made here are consistent with the choices made in the CGAL kernel, for which we refer the user to the 2D kernel manual.

In this first release, all functionalities necessary for computing an arrangement of circular arcs and these line segments are defined. Three traits classes are provided for the CGAL arrangement package.

4.2   Software Design

The design is done in such a way that the algebraic concepts and the geometric concepts are clearly separated. Circular_kernel_2 has therefore two template parameters:

• the LinearKernel, from which the circular kernel derives, provides all elementary geometric objects like points, lines, circles, and elementary functionality on them. It must be a model of the CGAL two dimensional Kernel concept.
• the second parameter is the algebraic kernel, which is responsible for computations on polynomials and algebraic numbers. It has to be a model of concept AlgebraicKernelForCircles. The robustness of the package relies on the fact that the algebraic kernel provides exact computations on algebraic objects.

The circular kernel uses the extensibility scheme presented in the 2D kernel manual (see Section 2.5). The types of LinearKernel are inherited by the circular kernel and some types are taken from the AlgebraicKernelForCircles parameter. Three new main geometric objects are introduced by Circular_kernel_2: circular arcs, points of circular arcs (used in particular for endpoints of arcs and intersection points between arcs) and line segments whose endpoints are points of this new type.

In fact, the circular kernel is documented as a concept, CircularKernel, and two models are provided:

• Circular_kernel_2<LinearKernel,AlgebraicKernelForCircles>, the basic kernel,
• and a predefined filtered kernel Exact_circular_kernel_2, that is based on similar techniques as Exact_predicates_exact_constructions_kernel.

4.3   Examples

4.3.1   Computing an Arrangement of Random Circles

This example shows how to construct incrementally an arrangement of circles, using the traits class for arrangement of circular arcs provided with the package.

File: examples/Circular_kernel_2/arrangement_random_circles.cpp

#include <CGAL/Cartesian.h>
#include <CGAL/Random.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Algebraic_kernel_for_circles_2_2.h>
#include <CGAL/Circular_kernel_2.h>
#include <CGAL/Arr_circular_arc_traits.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_naive_point_location.h>

typedef CGAL::Quotient<CGAL::MP_Float>                  NT;
typedef CGAL::Cartesian<NT>                             Linear_k;
typedef CGAL::Algebraic_kernel_for_circles_2_2<NT>      Algebraic_k;
typedef CGAL::Circular_kernel_2<Linear_k,Algebraic_k>   Circular_k;

typedef Circular_k::Point_2                             Point_2;
typedef Circular_k::Circle_2                            Circle_2;
typedef Circular_k::Circular_arc_2                      Circular_arc_2;
typedef std::vector<Circular_arc_2>                     ArcContainer;

typedef CGAL::Arr_circular_arc_traits<Circular_k>       Traits;

typedef CGAL::Arrangement_2<Traits>                     Arr;
typedef CGAL::Arr_naive_point_location<Arr>             Point_location;

int main(){

  CGAL::Random generatorOfgenerator;
  int random_seed = generatorOfgenerator.get_int(0, 123456);
  std::cout << "random_seed = " << random_seed << std::endl;
  CGAL::Random theRandom(random_seed);
  int random_max = 128;
  int random_min = -128;
  ArcContainer ac;
  int x, y;

  for (int i = 0; i < 10; i++) {
    x = theRandom.get_int(random_min,random_max);
    y = theRandom.get_int(random_min,random_max);
    ac.push_back( Circle_2( Point_2(x,y), x*x + y*y));
  }

  Arr  arr;
  Point_location _pl(arr);
  for (ArcContainer::const_iterator it=ac.begin(); it != ac.end(); ++it) {
    insert_curve(arr, *it, _pl);
  };

  return 0;
};

4.3.2   Constructing an Arrangement of Circles and Segments

In this example, the traits class using the boost::variant is used in order to provide arrangements with curves that can be either circular arcs or line segments.

File: examples/Circular_kernel_2/arrangement_random_circles_segments.cpp

#include <CGAL/Cartesian.h>
#include <CGAL/Random.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Algebraic_kernel_for_circles_2_2.h>
#include <CGAL/Circular_kernel_2.h>
#include <CGAL/Arr_circular_line_arc_traits.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_naive_point_location.h>

typedef CGAL::Quotient<CGAL::MP_Float>                  NT;
typedef CGAL::Cartesian<NT>                             Linear_k;
typedef CGAL::Algebraic_kernel_for_circles_2_2<NT>      Algebraic_k;
typedef CGAL::Circular_kernel_2<Linear_k,Algebraic_k>   Circular_k;
typedef Circular_k::Point_2                             Point_2;
typedef Circular_k::Circle_2                            Circle_2;
typedef Circular_k::Circular_arc_2                      Circular_arc_2;
typedef Circular_k::Line_arc_2                          Line_arc_2;

typedef boost::variant< Circular_arc_2, Line_arc_2>     Arc_2;
typedef std::vector< Arc_2>                             ArcContainer;

typedef CGAL::Arr_circular_line_arc_traits
<Circular_k, Circular_arc_2, Line_arc_2>                Traits;

typedef CGAL::Arrangement_2<Traits>                     Arr;
typedef CGAL::Arr_naive_point_location<Arr>             Point_location;

int main(){

  CGAL::Random generatorOfgenerator;
  int random_seed = generatorOfgenerator.get_int(0, 123456);
  std::cout << "random_seed = " << random_seed << std::endl;
  CGAL::Random theRandom(random_seed);
  int random_max = 128;
  int random_min = -128;
  ArcContainer ac;
  int x1, y1, x2, y2;

  for (int i = 0; i < 10; i++) {
    x1 = theRandom.get_int(random_min,random_max);
    y1 = theRandom.get_int(random_min,random_max);
    do{
      x2 = theRandom.get_int(random_min,random_max);
      y2 = theRandom.get_int(random_min,random_max);
    } while((x1 == x2) && (y1 == y2));
    std::cout << x1 << " " << y1 << " " << x2 << " " << y2 << std::endl;

    boost::variant< Circular_arc_2, Line_arc_2 >
      v =  Line_arc_2(Point_2(x1,y1), Point_2(x2,y2));
    ac.push_back( v);
  }

   for (int i = 0; i < 10; i++) {
    x1 = theRandom.get_int(random_min,random_max);
    y1 = theRandom.get_int(random_min,random_max);

    boost::variant< Circular_arc_2, Line_arc_2 >
      v = Circle_2( Point_2(x1,y1), x1*x1 + y1*y1);
    ac.push_back(v);
   }

  Arr arr;
  Point_location _pl(arr);
  for (ArcContainer::const_iterator it=ac.begin(); it != ac.end(); ++it) {
    insert_curve(arr, *it, _pl);
  };

  return 0;
};

4.3.3   Using the Predefined Kernel

File: examples/Circular_kernel_2/Exact_circular_kernel.cpp

#include <CGAL/basic.h>
#include <CGAL/Random.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/Exact_circular_kernel_2.h>
#include <CGAL/Arr_circular_line_arc_traits.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_naive_point_location.h>

typedef CGAL::Exact_circular_kernel_2                   Circular_k;

typedef Circular_k::Point_2                             Point_2;
typedef Circular_k::Circle_2                            Circle_2;
typedef Circular_k::Circular_arc_2                      Circular_arc_2;
typedef Circular_k::Line_arc_2                          Line_arc_2;

typedef boost::variant< Circular_arc_2, Line_arc_2>     Arc_2;
typedef std::vector< Arc_2> ArcContainer;

typedef CGAL::Arr_circular_line_arc_traits
              <Circular_k, Circular_arc_2, Line_arc_2>  Traits;

typedef CGAL::Arrangement_2<Traits>                            Arr;
typedef CGAL::Arr_naive_point_location<Arr>                 Point_location;

int main(){

  CGAL::Random generatorOfgenerator;
  int random_seed = generatorOfgenerator.get_int(0, 123456);
  std::cout << "random_seed = " << random_seed << std::endl;
  CGAL::Random theRandom(random_seed);
  int random_max = 128;
  int random_min = -128;
  ArcContainer ac;
  int x1, y1, x2, y2;

  for (int i = 0; i < 10; i++) {
    x1 = theRandom.get_int(random_min,random_max);
    y1 = theRandom.get_int(random_min,random_max);
    do{
      x2 = theRandom.get_int(random_min,random_max);
      y2 = theRandom.get_int(random_min,random_max);
    } while((x1 == x2) && (y1 == y2));
    std::cout << x1 << " " << y1 << " " << x2 << " " << y2 << std::endl;

    boost::variant< Circular_arc_2, Line_arc_2 >
      v =  Line_arc_2(Point_2(x1,y1), Point_2(x2,y2));
    ac.push_back( v);
  }

   for (int i = 0; i < 10; i++) {
    x1 = theRandom.get_int(random_min,random_max);
    y1 = theRandom.get_int(random_min,random_max);

    boost::variant< Circular_arc_2, Line_arc_2 >
      v = Circle_2( Point_2(x1,y1), x1*x1 + y1*y1);
    ac.push_back(v);
   }

  Arr _pm;
  Point_location _pl(_pm);
  for (ArcContainer::const_iterator it=ac.begin(); it != ac.end(); ++it) {
    insert_curve(_pm,*it,_pl);
  };

  return 0;
};

4.4   Design and Implementation History

The first pieces of prototype code were comparisons of algebraic numbers of degree 2, written by Olivier Devillers [DFMT00, DFMT02], and that are still used in the current implementation of CGAL::Root_of_2.

Some work was then done in the direction of a ``kernel'' for CGAL.¹ and the first design emerged in [EKP$$⁺04].

The code of this package was written by Sylvain Pion and Monique Teillaud who also wrote the manual. Athanasios Kakargias worked on an prototype version of this kernel in 2003. Julien Hazebrouck participated in the implementation of this kernel in July and August 2005. The contribution of Pedro Machado Manhães de Castro in summer 2006 improved significantly the efficiency of this kernel.

This work was partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG - Effective Computational Geometry for Curves and Surfaces).
This work is now partially supported by the IST Programme of the 6th Framework Programme of the EU as a STREP (FET Open Scheme) Project under Contract No IST-006413 (ACS - Algorithms for Complex Shapes).

Footnotes